package com.ly.algorithm.leetcode.tree;



import java.util.ArrayDeque;

/**
 * @Classname Problem116
 * @Description
 * 给定一个完美二叉树，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：
 *
 * struct Node {
 *   int val;
 *   Node *left;
 *   Node *right;
 *   Node *next;
 * }
 * 填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
 *
 * 初始状态下，所有 next 指针都被设置为 NULL。
 *

 * @Date 2020/10/15 19:55
 * @Author 冷心影翼
 */
public class Problem116 {

	public static void main(String[] args) {
		Node root = new Node(1);
		root.left = new Node(2);
		root.left.left = new Node(4);
		root.left.right = new Node(5);
		root.right = new Node(3);
		root.right.left = new Node(6);
		root.right.right = new Node(7);
		Solution116 solution116 = new Solution116();
		solution116.connectRecursion(root);
		System.out.println(root.next);
		System.out.println(root.left.right.next.val);
		System.out.println(root.right.next);
	}
}


class Solution116 {
	public Node connect(Node root) {
		if(root == null)
			return null;
		ArrayDeque<Node> queue = new ArrayDeque<>();
		queue.add(root);
		//1
		//3 2
		while (!queue.isEmpty()) {
			int size = queue.size();
			for(int i=0;i<size;i++) {
				Node poll = queue.poll();
				if(poll.left!=null)
					queue.add(poll.left);
				if(poll.right!=null)
					queue.add(poll.right);
				if(queue.peek()!=null && i+1!=size) {
					poll.next = queue.peek();
				}else {
					poll.next = null;
				}
			}
		}
		return root;
	}

	public Node connectRecursion(Node node) {
		if(node==null)
			return null;
		connectRecursion(node.left,node.right);
		return node;
	}

	public void connectRecursion(Node node1,Node node2) {
		if(node1 == null || node2 == null)
			return;
		node1.next = node2;
		connectRecursion(node1.left, node1.right);
		connectRecursion(node1.right,node2.left);
		connectRecursion(node2.left,node2.right);
	}
}